// or13  https://www.nowcoder.com/practice/585d46a1447b4064b749f08c2ab9ce66
// [贪心+二分查找]最长递增子序列LIS(Longest Increasing
// Subsequence)最长上升子序列
// 对于一个数字序列，请设计一个复杂度为O(nlogn)的算法，返回该序列的最长上升子序列的长度，
// 这里的子序列定义为这样一个序列U1，U2...，其中Ui < Ui+1，且A[Ui] < A[Ui+1]。
// 给定一个数字序列A及序列的长度n，请返回最长上升子序列的长度。
// 测试：[2,1,4,3,1,5,6],7
// 返回：4
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 9                                  //数组元素个数
int array[N] = {2, 1, 6, 3, 5, 4, 8, 7, 9};  //原数组
int dp[N];  //在动态规划中使用的数组,记录中间结果
int len;    //用于标示 dp 中的元素个数
//计算最长递增子序列的长度
int LIS(int *array, int n) {
  len = 1;
  dp[0] = array[0];
  for (int i = 1, pos = 0; i < n; ++i) {
    //如果大于最大的元素，则直接插入数组末尾
    if (array[i] > dp[len - 1]) {
      dp[len] = array[i];
      ++len;
    } else {
      pos = BiSearch(dp, len, array[i]);
      dp[pos] = array[i];
    }
  }
  return len;
}
//修改的二分查找，返回数组元素需要插入的位置
//数组b中不存在该元素，返回该元素应该插入的位置
int BiSearch(int *b, int nSize, int w) {
  int left = 0, right = nSize - 1;
  int mid;
  while (left <= right) {
    mid = left + (right - left) / 2;
    if (b[mid] > w)
      right = mid - 1;
    else if (b[mid] < w)
      left = mid + 1;
    else  //找到了该元素，则直接返回
      return mid;
  }
  return left;
}
int main() {
  printf("LIS: %d\n", LIS(array, N));
  int i;
  for (i = 0; i < len; ++i) {
    printf("dp[%d]=%d\n", i, dp[i]);
  }
  return 0;
}